package com.leetcode.August;

/**
 * @Description: 143. 重排链表
 * @Author: Mr.Fxy
 * @CreateTime: 2024-09-07 14:52
 */
public class LC143重排链表 {
    public void reorderList(ListNode head) {
        ListNode mid = middle(head);
        ListNode  head2= reverse(mid);
        while (head2.next!=null){
            ListNode nxt = head.next;
            ListNode nxt2 = head2.next;
            head.next=head2;
            head2.next=nxt;
            head=nxt;
            head2=nxt2;
        }
    }

    private ListNode middle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null, cur = head;
        while (cur != null){
            ListNode next = cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
}
